package leetcode.hard.maxSlidingWindow;

import util.annotation.Solved;

import java.util.PriorityQueue;

/**
 * <a href="https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked">239. 滑动窗口最大值</a>
 *
 * @since 2024-03-21
 */
@Solved
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o2[1]);
        int[] res = new int[nums.length - k + 1];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (queue.size() < k) {
                queue.offer(new int[] {nums[i], i});
            } else {
                // 当前窗口的最大元素
                res[j] = queue.peek()[0];
                j++;
                // 去除无用元素
                while (queue.peek() != null && queue.peek()[1] <= i - k) {
                    queue.poll();
                }
                queue.offer(new int[] {nums[i], i});
            }
        }
        res[res.length - 1] = queue.peek()[0];
        return res;
    }
}
